package binaryTreePackage;

import java.io.IOException;

import fileRandW.MyFileWriter;
import stackSinglyLinkListOperation.*;

public class BinaryTree {
	public BinaryTree() throws IOException {
		this.rootNode = new BSTNode();
		this.traversalMarker = null;
		this.myFileWriter = new MyFileWriter();

	}

	/**
	 * Function for inserting node Each data will be compared And insert in a
	 * proper sub-node
	 * 
	 * If this is the first time of calling this function,it will just save data in the root node.
	 * If not, it will call the following recursive function to insert the data
	 */
	public void insert(String readInData) {
		if (this.rootNode.getData() == null)
			this.rootNode.saveData(readInData);
		else
			insertNode(this.rootNode, readInData);

	}
/**
 * Used when the root node already has data inside
 * @param currentNode
 * @param data
 */
	public void insertNode(BSTNode currentNode, String data) {
		if ((data.compareTo(currentNode.getData()) < 0)) {
			if (currentNode.LeftChild == null) {
				//Create a node for saving data
				BSTNode newNode = new BSTNode();
				newNode.saveData(data);
				currentNode.LeftChild = newNode;
			} else
				insertNode(currentNode.LeftChild, data);
		} else {
			if (currentNode.RightChild == null) {
				//Create a node for saving data
				BSTNode newNode = new BSTNode();
				newNode.saveData(data);
				currentNode.RightChild = newNode;
			} else
				insertNode(currentNode.RightChild, data);
		}

	}

	/**
	 * Function for checking whether the tree is empty
	 */
	public void inEmpty() {
		if (this.rootNode.getData() == null)
			System.out.println("This tree is empty");
		else
			System.out.println("This tree is not empty");

	}

	/**
	 * Preorder Traversal, a node is visited before its descendants OK
	 * 
	 * @throws IOException
	 */
	public void preOrederTraversal() throws IOException {
		this.myFileWriter.wirteTXT("Preorder traversal start   \n");
		System.out.println("Preorder traversal start");
		tempNode = rootNode;
		PrivateStack myStack = new PrivateStack();
		myStack.push(tempNode);
		int tempCount = 0;
		while (myStack.isEmpty() == false) {
			tempCount++;
			tempNode = myStack.pop();
			System.out.println("This is  " + tempCount + "  data   "
					+ tempNode.getData());
			this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
			// write the file
			System.out.println(tempNode);
			if (tempNode.RightChild != null) {
				myStack.push(tempNode.RightChild);
				System.out.println("This is right child's  data "
						+ tempNode.RightChild.getData());
				System.out.println("This is right child  "
						+ tempNode.RightChild);
			}
			if (tempNode.LeftChild != null) {
				myStack.push(tempNode.LeftChild);
				System.out.println("This is left child's left data "
						+ tempNode.LeftChild.getData());
				System.out.println("This is left child " + tempNode.LeftChild);

			}
			
		}
		this.myFileWriter.closeMyFile();
	}

	/**
	 * Postorder Traversal, a node is visited after its descendants
	 * 
	 * @throws IOException
	 */
	public void postOrderTraversal() throws IOException {
		this.myFileWriter.wirteTXT("Postorder traversal start   \n");
		System.out.println("Postorder traversal start");
		PrivateStack myStack = new PrivateStack();
		tempNode = rootNode;
		int tempCount = 0;
		while (tempNode != null) {
			while (tempNode.LeftChild != null) {
				myStack.push(tempNode);
				tempNode = tempNode.LeftChild;
			}
			while (tempNode.RightChild == null
					|| this.traversalMarker == tempNode.RightChild) {
				tempCount++;
				System.out.println("This is " + " " + tempCount + " "
						+ tempNode.getData());
				this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
				this.traversalMarker = tempNode;
				if (myStack.isEmpty() == true) {
					this.myFileWriter.closeMyFile();
					return;
				}
				tempNode = myStack.pop();
			}
			myStack.push(tempNode);
			tempNode = tempNode.RightChild;
		}
		this.myFileWriter.closeMyFile();

	}

	/**
	 * Inorder Traversal, a node is visited after its left subtree and before
	 * its right subtree
	 * 
	 * @throws IOException
	 */
	public void inOrderTraversal() throws IOException {
		this.myFileWriter.wirteTXT("Inorder traversal start   \n");
		System.out.println("Inorder traversal start");
		PrivateStack myStack = new PrivateStack();
		tempNode = rootNode;
		int tempCount = 0;
		while (tempNode != null) {
			while (tempNode != null) {
				if (tempNode.RightChild != null)
					myStack.push(tempNode.RightChild);
				myStack.push(tempNode);
				tempNode = tempNode.LeftChild;
			}
			// When the above loop breaks, it means that the most left node is
			// the top element in the stack
			tempNode = myStack.pop();
			tempCount++;
			System.out.println("this is the   " + tempCount + " data  "
					+ tempNode.getData());
			this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
			while (tempNode.RightChild == null) {
				if (myStack.isEmpty() == true) {
					this.myFileWriter.closeMyFile();
					return;
				}
				tempNode = myStack.pop();
				tempCount++;
				System.out.println("this is the   " + tempCount + " data  "
						+ tempNode.getData());
				this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
			}
			tempNode = myStack.pop();

		}

	}
	/**
	 * Inorder R TO L traversal,just reverse the sequence of traditional inorder traversal
	 * @throws IOException
	 */
public void RtoLinOrderTraversal() throws IOException{
	this.myFileWriter.wirteTXT("R-L   Inorder traversal start   \n");
	System.out.println("Inorder traversal start");
	PrivateStack myStack = new PrivateStack();
	tempNode = rootNode;
	int tempCount = 0;
	while (tempNode != null) {
		while (tempNode != null) {
			if (tempNode.LeftChild != null)
				myStack.push(tempNode.LeftChild);
			myStack.push(tempNode);
			tempNode = tempNode.RightChild;
		}
		// When the above loop breaks, it means that the most left node is
		// the top element in the stack
		tempNode = myStack.pop();
		tempCount++;
		System.out.println("this is the   " + tempCount + " data  "
				+ tempNode.getData());
		this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
		while (tempNode.LeftChild == null) {
			if (myStack.isEmpty() == true) {
				this.myFileWriter.closeMyFile();
				return;
			}
			tempNode = myStack.pop();
			tempCount++;
			System.out.println("this is the   " + tempCount + " data  "
					+ tempNode.getData());
			this.myFileWriter.wirteTXT(tempNode.getData() + "    \n");
		}
		tempNode = myStack.pop();

	}
	
}
	public BSTNode getRootNode() {
		return rootNode;
	}

	private BSTNode rootNode;
	private BSTNode tempNode;
	private BSTNode traversalMarker;
	private MyFileWriter myFileWriter;
}
